import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        Solution test = new Solution();
        // System.out.println(test.findSubstringInWraproundString("zab"));

        int[] nums = new int[]{10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println(test.lengthOfLIS(nums));
    }


    public int findSubstringInWraproundString(String s) {
        /**
         * 环绕字符串中唯一的子字符串
         *  状态表示：
         *      dp[i]表示以i下标元素为结尾的所有子字符串中，不同非空子串的个数
         *  状态转移方程：
         *      if((s.charAt(i) - s.charAt(i-1) == 1) || (s.charAt(i) == 'b' && s.charAt(i-1) == 'a')) {
         *          dp[i] = dp[i-1] + 1;
         *      }
         *  初始化：
         *      由状态转移方程可知，在填写i下标状态时会使用到i-1的状态，因此在填写0状态时会出现数组越界访问的情况
         *      为了避免，故手动赋值
         *      再者，由题可知，单个字符也视为一个不同非空子串，因此dp表中最长状态为1，可在初始化时统一处理
         *  返回值：
         *      返回去重后的和
         * */
        // 1 预处理
        int n = s.length();
        // 2 创建dp表
        int[] dp = new int[n];
        // 3 初始化
        Arrays.fill(dp, 1);
        // 4 填表
        // - 创建去重表
        // - 由于此处需要多次手动初始化赋值，因此还是使用虚拟位置法会更加妥当
        int[] dropDuplicatedArray = new int[26];
        dropDuplicatedArray[s.charAt(0) - 'a'] = 1;
        for(int i = 1; i < n; i++) {
            if((s.charAt(i) - s.charAt(i-1) == 1) || (s.charAt(i) == 'a' && s.charAt(i-1) == 'z')) {
                dp[i] = dp[i-1] + 1;
            }
            // - 添加至去重表中，字母对应下标位置
            if(dropDuplicatedArray[s.charAt(i) - 'a'] < dp[i]) {
                dropDuplicatedArray[s.charAt(i) - 'a'] = dp[i];
            }
        }
        // 5 返回值
        return Arrays.stream(dropDuplicatedArray).sum();
    }

    public int lengthOfLIS(int[] nums) {
        /**
         * 最长递增子序列
         *  状态表示：
         *      dp[i]表示以i下标元素为结尾的所有子序列中，最长递增子序列的长度
         *  状态转移方程：
         *      if(nums[i] > nums[j]) {
         *          dp[i] = Math.max(dp[i], dp[j] + 1);
         *      }
         *  初始化：
         *      由题可知，单个元素也是一个递增子序列，且长度为1，故使用最差情况初始化dp表
         *  填表顺序：
         *      从左到右
         *  返回值：
         *      返回dp表中的最大值
         * */
        // 1 初始化
        int n = nums.length;
        // 2 创建dp表
        int[] dp = new int[n];
        // 3 初始化
        Arrays.fill(dp, 1);
        // 4 填表
        int maxLength = 1;
        for(int i = 0; i < n; i ++) {
            for(int j = i-1; j >= 0; j --) {
                if(nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            // - 求最大值
            if(maxLength < dp[i]) {
                maxLength = dp[i];
            }
        }
        // 5 返回值
        return maxLength;
    }
}
